
#ifndef __FINDINGEXTREMITIES_H
#define __FINDINGEXTREMITIES_H

//~ Variaveis globais
//~ int num_extremities = 5;
//~ int parent[100];
//~ vertex handle farthest_vertex = 0;

void floodfill_Finding_Extremities(unsigned idv, int num_extremities);

void Finding_Extremities(Mesh *mesh) {
   
   
}

void floodfill_Finding_Extremities(Mesh *mesh, unsigned idv, int num_extremities) {

   cout<<"flood_fill(mesh) ... begin "<<endl;
   /// initializing
   Vertex_iterator vi = mesh->vertices_begin();
   for ( unsigned int i=0; i<mesh->size_of_vertices(); i++) {
    vi[i].d = NINFINITY;
   }
   Vertex_handle h = vi[idv].halfedge()->vertex();

   h->d = 0;
   float dmax = 0;
   vertex handle vmax =h;
   int nvertices_covered =1;
   parent[0] = -1;
   farthest_vertex[0] = 0;
   priority_queue<Vertex_handle, vector<Vertex_handle>, compareuv>
   queue_vertices;
   queue_vertices.push(h);
   for(i=0;i<num_extremities;i++) {
      while (not queue_vertices.empty()) {
         Vertex_handle u = queue_vertices.top();
         queue_vertices.pop();
         Halfedge_handle hh = u->halfedge(), hhbegin = hh;
         if(u->d > dmax){
            dmax = u->d;
            vmax =u;
         }
         do {
            Vertex_handle v = hh->opposite()->vertex();
            const Point3 &pv = v->point();
            const Point3 &pu = u->point();
            const Vector3 uv(pv[0]-pu[0],pv[1]-pu[1],pv[2]-pu[2]);
            const Number duv = sqrt(uv*uv);
            if (u->d + duv < v->d) {
                v->d = u->d + duv;
                v->previous(u);
                queue_vertices.push(v);
            }
            hh = hh->next()->opposite(); //
         } while(hh != hhbegin);
      }
      
      vertex handle w =vmax;
      queue_vertices.push(vmax);
      vmax->d = 0;
      do {
         w =w->previous;
         w->d =0;
         w->label = i;
         queue_vertices.push(w);
         n_vertices_covered ++;
      } (while w->d != 0);
      
      parent[i]= w->label;
      nvertices_covered --;
      if (nvertices_covered >= mesh->size_of_vertices()) break;
   }
   cout<<"flood_fill(mesh) ... end"<<endl;
}

#endif
